package com.zhengb.algorithmdemo.leetcode.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
 * <p>
 * 说明：
 * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author zhengbo
 * @date 2020/3/10
 */
public class KthSmallest {

    /**
     * 非递归中序遍历二叉树
     *
     * @param rootNode
     * @return
     */
    private static List<Integer> traverseTreeWithInOrder(TreeNode rootNode) {

        List<Integer> resultList = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();

        TreeNode tempNode = rootNode;

        while (true) {
            while (tempNode != null) {
                stack.push(tempNode);
                tempNode = tempNode.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            tempNode = stack.pop();
            resultList.add(tempNode.val);

            tempNode = tempNode.right;
        }

        return resultList;
    }

    /**
     * 递归中序遍历二叉树
     *
     * @param root
     * @param list
     */
    public static void inOrderTraverseWithRecursive(TreeNode root, List<Integer> list) {

        if (root != null) {
            inOrderTraverseWithRecursive(root.left, list);
            list.add(root.val);
            inOrderTraverseWithRecursive(root.right, list);
        }

    }


    /**
     * 解决思路 使用中序遍历二叉树 得到排序好的列表
     *
     * @param root
     * @param k
     * @return
     */
    public static int kthSmallest(TreeNode root, int k) {

        List<Integer> traverseList = new ArrayList<>();

        inOrderTraverseWithRecursive(root, traverseList);

        return traverseList.get(k - 1);
    }


    public static void main(String[] args) {

        TreeNode one = new TreeNode(1);
        TreeNode two = new TreeNode(2);
        TreeNode three = new TreeNode(3);
        TreeNode four = new TreeNode(4);
        TreeNode five = new TreeNode(5);
        TreeNode six = new TreeNode(6);

        five.left = three;
        five.right = six;

        three.left = two;
        three.right = four;

        two.left = one;

        int result = kthSmallest(five, 3);

        System.out.println(result);
    }
}
